package class04;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @description: 利用链表实现队列和栈
 * @time: 2021/7/17 16:56
 * @author: lhy
 */
public class LinkedListToQueueAndStack {
    public static class Node<V> {
        V val;
        Node<V> next;
        public Node(V val){
            this.val = val;
        }
    }

    public static class MyQueue<V>{
        private Node<V> head;
        private Node<V> tail;
        private int size;
        public MyQueue(){
            this.head = null;
            this.tail = null;
            this.size = 0;
        }
        public boolean isEmpty(){
            return size == 0;
        }
        public int size(){
            return size;
        }
        public void add(V value){
            Node<V> cur = new Node<>(value);
            if (tail == null) {
                head = cur;
            }else {
                tail.next = cur;
            }
            tail = cur;
            size++;
        }
        public V poll(){
            V ans = null;
             if (head != null){
                ans = head.val;
                head = head.next;
                size--;
             }
            if (head == null) {
                tail = null;
            }
            return ans;
        }

        public V peek(){
            V ans = null;
            if (head != null){
                ans = head.val;
            }
            return ans;
        }
    }

    public static class MyStack<V>{
        private Node<V> head;
        private int size;
        public MyStack(){
            this.head = null;
            this.size = 0;
        }
        public boolean isEmpty(){
            return size == 0;
        }
        public int size(){
            return size;
        }
        public void push(V value){
            Node<V> cur = new Node<>(value);
            if (head != null) {
                cur.next = head;
            }
            head = cur;
            size++;
        }
        public V pop(){
            V ans = null;
            if (head != null){
                ans = head.val;
                head = head.next;
                size--;
            }
            return ans;
        }

        public V peek(){
            return head != null ? head.val : null;
        }
    }


    public static void testQueue(int testTime, int maxValue) {
        MyQueue<Integer> myQueue = new MyQueue<>();
        Queue<Integer> test = new LinkedList<>();
        System.out.println("MyQueue test begin...");
        for (int i = 0; i < testTime; i++) {
            if (myQueue.isEmpty() != test.isEmpty()) {
                System.out.println("myQueue.isEmpty() Oops!");
            }
            if (myQueue.size() != test.size()) {
                System.out.println("myQueue.size() Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                myQueue.add(num);
                test.add(num);
            } else if (decide < 0.66) {
                if (!myQueue.isEmpty()) {
                    int num2 = test.poll();
                    int num1 = myQueue.poll();
                    if (num1 != num2) {
                        System.out.println("myQueue.poll() Oops!");
                    }
                }
            } else {
                if (!myQueue.isEmpty()) {
                    int num2 = test.peek();
                    int num1 = myQueue.peek();

                    if (num1 != num2) {
                        System.out.println("myQueue.peek() Oops!");
                    }
                }
            }
        }
        if (myQueue.size() != test.size()) {
            System.out.println("myQueue.size() Oops!");
        }
        while (!myQueue.isEmpty()) {
            int num1 = myQueue.poll();
            int num2 = test.poll();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("MyQueue test end！");
    }

    public static void testStack(int testTime, int maxValue) {
        MyStack<Integer> myStack = new MyStack<>();
        Stack<Integer> test = new Stack<>();
        System.out.println("MyStack test begin...");
        for (int i = 0; i < testTime; i++) {
            if (myStack.isEmpty() != test.isEmpty()) {
                System.out.println("myStack.isEmpty() Oops!");
            }
            if (myStack.size() != test.size()) {
                System.out.println("myStack.size() Oops!");
            }
            double decide = Math.random();
            if (decide < 0.33) {
                int num = (int) (Math.random() * maxValue);
                myStack.push(num);
                test.push(num);
            } else if (decide < 0.66) {
                if (!myStack.isEmpty()) {
                    int num1 = myStack.pop();
                    int num2 = test.pop();
                    if (num1 != num2) {
                        System.out.println("myStack.pop() Oops!");
                    }
                }
            } else {
                if (!myStack.isEmpty()) {
                    int num1 = myStack.peek();
                    int num2 = test.peek();
                    if (num1 != num2) {
                        System.out.println("myStack.peek() Oops!");
                    }
                }
            }
        }
        if (myStack.size() != test.size()) {
            System.out.println("myStack.size() Oops!");
        }
        while (!myStack.isEmpty()) {
            int num1 = myStack.pop();
            int num2 = test.pop();
            if (num1 != num2) {
                System.out.println("Oops!");
            }
        }
        System.out.println("MyStack test end！");
    }

    public static void main(String[] args) {
        int testTime = 5000000;
        int maxValue = 200000000;
        double p = 0.33;
        testQueue(testTime,maxValue);
        testStack(testTime,maxValue);
    }
}
